package com.zlk.algorithm.algorithm.dynamicPlan.PartitionedKnapsack074;

import java.io.*;
import java.util.*;

// 分组背包(模版)
// 给定一个正数m表示背包的容量，有n个货物可供挑选
// 每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)
// 同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量
// 怎么挑选货物能达到价值最大，返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1757
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
// 数据规模
//0《=m<=1000  1<=n<=1000   1《=k<=100
public class Code01_PartitionedKnapsack {


    public static int MAXN = 1001;

    public static int MAXM = 1001;

    static int[] cost = new int[MAXM];
    static int[] val = new int[MAXM];

    static HashMap<Integer, List> group = new HashMap<>();


    public static int[] dp = new int[MAXM];

    //给定一个正数m表示背包的容量，有n个货物可供挑选
    //  30      6
    //  4   5  1
    //  8   4  1
    //  5   4  2
    //  5   5  2
    //  7   5  3
    //  9   6  4

    public static int m, n,index;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            clean();
            m = (int) in.nval;
            in.nextToken();
            n = (int) in.nval;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                cost[i] = (int) in.nval;
                in.nextToken();
                val[i] = (int) in.nval;
                in.nextToken();
                int g = (int) in.nval;
                List list = group.get(g);
                if(list== null){
                    index++;
                    list = new ArrayList();
                }
                list.add(i);
                group.put(index,list);
            }
            out.println(compute1());
        }
        out.flush();
        out.close();
        br.close();
    }

    private static void clean() {
        index=0;
        group = new HashMap<>();
    }


    // 同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量
    // 怎么挑选货物能达到价值最大，返回最大的价值
    private static int compute1() {
        Set<Map.Entry<Integer, List>> entries = group.entrySet();
        for (Map.Entry<Integer, List> entry : entries) {
            List nums = entry.getValue();
            for (int i = 0; i < nums.size(); i++) {
                int c = cost[(int)nums.get(i)];
                int v = val[(int)nums.get(i)];
                for (int j = m; j >=c ; j++) {
                    dp[j] = Math.max(dp[j],dp[j-c]+v);
                }
            }
        }
        return dp[m];
    }


}
